package com.fallsvc.re.javasesets.mapandset.binarysearchtree;

/**
 * @auther falls_vc
 * description:
 * @date 2025/10/22  14:53
 */
public class MyBinarySearchTree {

    public static class Node {
        int key;
        Node left;
        Node right;
        public Node(int key) {
            this.key = key;
        }
    }
    private Node root = null;
    /**
     * 在搜索树中查找 key，如果找到，返回 key 所在的结点，否则返回 null
     * @param key
     * @return
     */
    public Node search(int key) {
        Node cur = root;
        while (cur != null) {
            if (key == cur.key) {
                return cur;
            } else if (key < cur.key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return null;
    }
    /**
     * * 插入
    * @param key
    * @return true 表示插入成功, false 表示插入失败
    */
    public boolean insert(int key) {
        if (root == null) {
            root = new Node(key);
            return true;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (key == cur.key) {
                return false;
            } else if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }
        Node node = new Node(key);
        if (key < parent.key) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        return true;
    }

    /**
     * 删除成功返回 true，失败返回 false
     * @param key
    * @return
    */
    public boolean remove(int key) {
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (key == cur.key) {
                break;
            } else if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }
        // 该元素不在二叉搜索树中
        if (null == cur) {
            return false;
        }

        // 删除节点 TODO
        //1. cur左右孩子均不存在
        //2. cur只有左孩子
        //3. cur只有右孩子
        //4. cur左右孩子均存在
        return true;
    }
}
